﻿#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>


//(1)  反转字符串
//写出⼀个程序, 接受⼀个字符串, 然后输出该字符串反转后的字符串。
//(字符串⻓度不超过1000)
//数据范围:0くn≤1000
//要求 : 空间复杂度O(n), 时间复杂度O(n)


//解法一
//使⽤⼀个格外的数组，来存储结果，原数组从后往前遍历，依次将元素存储

char* solve1(char* str)
{
	int len = (int)strlen(str);
	char* tmp = (char*)malloc(sizeof(char) * (len + 1));//多开辟一个用来存放\0
	assert(tmp != NULL);
	int i = 0;
	int end = len - 1;
	while (end>=0)
	{
		tmp[i++] = str[end--];
	}
	tmp[i] = '\0';
	strcpy(str, tmp);
	free(tmp);
	tmp = NULL;
	return str;
}


//解法二
//使⽤类似于双指针法的⽅式，定义begin，end两个位置来标定交换，对于字符串⾸尾交换
char* solve2(char* str)
{
	int len = (int)strlen(str);
	int begin = 0;
	int end = len - 1;
	while (begin < end)
	{
		char tmp = str[begin];
		str[begin] = str[end];
		str[end] = tmp;
		begin++;
		end--;
	}
	return str;
}


//解法三
//利⽤递归的思路，先是压栈到最后⼀个元素处，然后再跟第⼀个元素交换，然后栈帧回退，接着倒数第⼆个元素跟第⼆个元素交换，
//如此往复，最终字符串反转完。
void reverse(char* str)
{
	int len = (int)strlen(str);;//获取当前函数栈帧下字符串的⻓度
	if (len <= 1)
	{
		return;
	}
	char tmp = str[0];
	str[0] = str[len - 1];
	str[len - 1] = '\0';
	reverse(str + 1);
	str[len - 1] = tmp;;//当递归结束回退的时候，将每个函数栈帧下的⾸元素重新填充到当前函数栈帧字符串的最后
}
char* solve3(char* str)
{
	reverse(str);
	return str;
}


int main()
{
	char arr[20] = "Hello World";
	/*char* newarr = solve1(arr);*/
	/*char* newarr = solve2(arr);*/
	char* newarr = solve3(arr);
	printf("%s\n", newarr);
	return 0;
}